import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Map;
import java.util.concurrent.*;
import java.util.concurrent.atomic.AtomicReference;

/**
 * @author:hillchen
 * @DESCRIPTION:
 * @Date: Created in 14:15 2018/2/11 0011.
 */
public class MazeDemo {
    private static int[][] createMaze(int times){
        int[][] baseMaze = new int[][]{
                {0,0,0,1,1,1,1,1,1,1,0,1,1,1,1,1,1,1,1,1,0,1,1,1,1,1,1,1,1,1,0,1,1,1,1,1,1,1,1,1},
                {0,0,0,0,0,0,0,1,0,1,0,0,0,0,0,0,0,1,0,1,0,0,0,0,0,0,0,1,0,1,0,0,0,0,0,0,0,1,0,1},
                {0,0,1,0,1,1,0,0,0,1,1,0,1,0,1,1,0,0,0,1,1,0,1,0,1,1,0,0,0,1,1,0,1,0,1,1,0,0,0,1},
                {1,0,1,1,1,1,1,0,1,0,1,0,1,1,1,1,1,0,1,0,1,0,1,1,1,1,1,0,1,0,1,0,1,1,1,1,1,0,1,0},
                {1,0,0,0,0,0,1,0,1,1,1,0,0,0,0,0,1,0,1,1,1,0,0,0,0,0,1,0,1,1,1,0,0,0,0,0,1,0,1,1},
                {1,1,1,1,1,0,0,0,0,0,1,1,1,1,1,0,0,0,0,0,1,1,1,1,1,0,0,0,0,0,1,1,1,1,1,0,0,0,0,0},
                {1,0,0,0,0,0,1,0,1,0,1,0,0,0,0,0,1,0,1,0,1,0,0,0,0,0,1,0,1,0,1,0,0,0,0,0,1,0,1,0},
                {1,0,1,1,1,0,0,0,1,1,1,0,1,1,1,0,0,0,1,1,1,0,1,1,1,0,0,0,1,1,1,0,1,1,1,0,0,0,1,1},
                {1,0,0,0,0,1,1,1,0,1,1,0,0,0,0,1,1,1,0,1,1,0,0,0,0,1,1,1,0,1,1,0,0,0,0,1,1,1,0,1},
                {1,1,1,1,0,0,0,0,0,0,0,1,1,1,0,0,0,0,0,0,1,1,1,1,0,0,0,0,0,0,1,1,1,1,0,0,0,0,0,0},
                {0,1,1,1,1,1,1,1,1,1,0,1,1,1,1,1,1,1,1,1,0,1,1,1,1,1,1,1,1,1,0,1,1,1,1,1,1,1,1,1},
                {0,0,0,0,0,0,0,1,0,1,0,0,0,0,0,0,0,1,0,1,0,0,0,0,0,0,0,1,0,1,0,0,0,0,0,0,0,1,0,1},
                {1,0,1,0,1,1,0,0,0,1,1,0,1,0,1,1,0,0,0,1,1,0,1,0,1,1,0,0,0,1,1,0,1,0,1,1,0,0,0,1},
                {1,0,1,1,1,1,1,0,1,0,1,0,1,1,1,1,1,0,1,0,1,0,1,1,1,1,1,0,1,0,1,0,1,1,1,1,1,0,1,0},
                {1,0,0,0,0,0,1,0,1,1,1,0,0,0,0,0,1,0,1,1,1,0,0,0,0,0,1,0,1,1,1,0,0,0,0,0,1,0,1,1},
                {1,1,1,1,1,0,0,0,0,0,1,1,1,1,1,0,0,0,0,0,1,1,1,1,1,0,0,0,0,0,1,1,1,1,1,0,0,0,0,0},
                {1,0,0,0,0,0,1,0,1,0,1,0,0,0,0,0,1,0,1,0,1,0,0,0,0,0,1,0,1,0,1,0,0,0,0,0,1,0,1,0},
                {1,0,1,1,1,0,0,0,1,1,1,0,1,1,1,0,0,0,1,1,1,0,1,1,1,0,0,0,1,1,1,0,1,1,1,0,0,0,1,1},
                {1,0,0,0,0,1,1,1,0,1,1,0,0,0,0,1,1,1,0,1,1,0,0,0,0,1,1,1,0,1,1,0,0,0,0,1,1,1,0,1},
                {1,1,1,1,0,0,0,0,0,0,1,1,1,1,0,0,0,0,0,0,0,1,1,1,0,0,0,0,0,0,1,1,1,1,0,0,0,0,0,0},
                {0,1,1,1,1,1,1,1,1,1,0,1,1,1,1,1,1,1,1,1,0,1,1,1,1,1,1,1,1,1,0,1,1,1,1,1,1,1,1,1},
                {0,0,0,0,0,0,0,1,0,1,0,0,0,0,0,0,0,1,0,1,0,0,0,0,0,0,0,1,0,1,0,0,0,0,0,0,0,1,0,1},
                {1,0,1,0,1,1,0,0,0,1,1,0,1,0,1,1,0,0,0,1,1,0,1,0,1,1,0,0,0,1,1,0,1,0,1,1,0,0,0,1},
                {1,0,1,1,1,1,1,0,1,0,1,0,1,1,1,1,1,0,1,0,1,0,1,1,1,1,1,0,1,0,1,0,1,1,1,1,1,0,1,0},
                {1,0,0,0,0,0,1,0,1,1,1,0,0,0,0,0,1,0,1,1,1,0,0,0,0,0,1,0,1,1,1,0,0,0,0,0,1,0,1,1},
                {1,1,1,1,1,0,0,0,0,0,1,1,1,1,1,0,0,0,0,0,1,1,1,1,1,0,0,0,0,0,1,1,1,1,1,0,0,0,0,0},
                {1,0,0,0,0,0,1,0,1,0,1,0,0,0,0,0,1,0,1,0,1,0,0,0,0,0,1,0,1,0,1,0,0,0,0,0,1,0,1,0},
                {1,0,1,1,1,0,0,0,1,1,1,0,1,1,1,0,0,0,1,1,1,0,1,1,1,0,0,0,1,1,1,0,1,1,1,0,0,0,1,1},
                {1,0,0,0,0,1,1,1,0,1,1,0,0,0,0,1,1,1,0,1,1,0,0,0,0,1,1,1,0,1,1,0,0,0,0,1,1,1,0,1},
                {1,1,1,1,0,0,0,0,0,0,1,1,1,1,0,0,0,0,0,0,1,1,1,1,0,0,0,0,0,0,0,1,1,1,0,0,0,0,0,0},
                {0,1,1,1,1,1,1,1,1,1,0,1,1,1,1,1,1,1,1,1,0,1,1,1,1,1,1,1,1,1,0,1,1,1,1,1,1,1,1,1},
                {0,0,0,0,0,0,0,1,0,1,0,0,0,0,0,0,0,1,0,1,0,0,0,0,0,0,0,1,0,1,0,0,0,0,0,0,0,1,0,1},
                {1,0,1,0,1,1,0,0,0,1,1,0,1,0,1,1,0,0,0,1,1,0,1,0,1,1,0,0,0,1,1,0,1,0,1,1,0,0,0,1},
                {1,0,1,1,1,1,1,0,1,0,1,0,1,1,1,1,1,0,1,0,1,0,1,1,1,1,1,0,1,0,1,0,1,1,1,1,1,0,1,0},
                {1,0,0,0,0,0,1,0,1,1,1,0,0,0,0,0,1,0,1,1,1,0,0,0,0,0,1,0,1,1,1,0,0,0,0,0,1,0,1,1},
                {1,1,1,1,1,0,0,0,0,0,1,1,1,1,1,0,0,0,0,0,1,1,1,1,1,0,0,0,0,0,1,1,1,1,1,0,0,0,0,0},
                {1,0,0,0,0,0,1,0,1,0,1,0,0,0,0,0,1,0,1,0,1,0,0,0,0,0,1,0,1,0,1,0,0,0,0,0,1,0,1,1},
                {1,0,1,1,1,0,0,0,1,1,1,0,1,1,1,0,0,0,1,1,1,0,1,1,1,0,0,0,1,1,1,0,1,1,1,0,0,0,1,0},
                {1,0,0,0,0,1,1,1,0,1,1,0,0,0,0,1,1,1,0,1,1,0,0,0,0,1,1,1,0,1,1,0,0,0,0,1,1,1,0,0},
                {0,1,1,1,0,0,0,0,0,0,1,1,1,1,0,0,0,0,0,0,1,1,1,1,0,0,0,0,0,0,1,1,1,1,0,0,0,0,0,0}
        };
        int baseXLength = baseMaze.length;
        int baseYLength =  baseMaze[0].length;
        int yLength = baseXLength * times;
        int xLength =baseYLength * times;
        int[][] retMaze = new int[xLength][yLength];
        for(int y=0;y<yLength;y++){
            for(int x=0;x<xLength;x++){
                retMaze[x][y] = baseMaze[x%baseXLength][y%baseYLength];
            }
        }
        return retMaze;

    }

    static class Point{
        int x;
        int y;

        public Point(int x, int y) {
            this.x = x;
            this.y = y;
        }

        @Override
        public boolean equals(Object o) {
            if (this == o) return true;
            if (o == null || getClass() != o.getClass()) return false;

            Point point = (Point) o;

            if (x != point.x) return false;
            return y == point.y;

        }

        @Override
        public int hashCode() {
            int result = x;
            result = 31 * result + y;
            return result;
        }
    }

    static class RouteNode{
        RouteNode lastRouteNode;
        Point currenPoint;

        public RouteNode(RouteNode lastRouteNode, Point currenPoint) {
            this.lastRouteNode = lastRouteNode;
            this.currenPoint = currenPoint;
        }
    }

    static class SearchThread implements Runnable{
        private final Point currentPoint;
        private final RouteNode lastNode;
        private final ExecutorService executorService;
        private final CountDownLatch endLatch;
        private final int[][] maze;
        private final Map<Point,List<RouteNode>> searcedNodes;
        private final AtomicReference<RouteNode> endNode;

        public SearchThread(Point currentPoint, RouteNode lastNode, ExecutorService executorService, CountDownLatch endLatch,
                            int[][] maze, Map<Point, List<RouteNode>> searcedNodes, AtomicReference<RouteNode> endNode) {
            this.currentPoint = currentPoint;
            this.lastNode = lastNode;
            this.executorService = executorService;
            this.endLatch = endLatch;
            this.maze = maze;
            this.searcedNodes = searcedNodes;
            this.endNode = endNode;
        }

        @Override
        public void run() {
            System.out.println(String.format("##########开始搜索节点(%s,%s)",currentPoint.x,currentPoint.y));
            int maxY = maze.length;
            int maxX = maze[0].length;
            int currentX = currentPoint.x;
            int currentY = currentPoint.y;
            if(!searcedNodes.containsKey(currentPoint)){
                List<RouteNode> routeNodes = Collections.synchronizedList(new ArrayList<>());
                searcedNodes.putIfAbsent(currentPoint,routeNodes);
            }
            List<RouteNode>  routeNodes = searcedNodes.get(currentPoint);
            routeNodes.add(lastNode);

            if(currentY < maxY -1){
                int nextY = currentY + 1;
                if(maze[nextY][currentX] == 0){
                    searchNextRouteNode(executorService,endLatch,maze,searcedNodes,new Point(currentX,nextY),new RouteNode(lastNode,currentPoint),endNode);
                }
            }
            if(currentY > 0){
                int nextY = currentY - 1;
                if(maze[nextY][currentX] == 0){
                    searchNextRouteNode(executorService,endLatch,maze,searcedNodes,new Point(currentX,nextY),new RouteNode(lastNode,currentPoint),endNode);
                }
            }
            if(currentX > 0){
                int nextX = currentX - 1;
                if(maze[currentY][nextX] == 0){
                    searchNextRouteNode(executorService,endLatch,maze,searcedNodes,new Point(nextX,currentY),new RouteNode(lastNode,currentPoint),endNode);
                }
            }
            if(currentX < maxX -1){
                int nextX = currentX + 1;
                if(maze[currentY][nextX] == 0){
                    searchNextRouteNode(executorService,endLatch,maze,searcedNodes,new Point(nextX,currentY),new RouteNode(lastNode,currentPoint),endNode);
                }
            }
        }
    }

    private static void searchNextRouteNode(final ExecutorService executorService, final CountDownLatch endLatch,final int[][]maze,final Map<Point,List<RouteNode>> searcedNodes,
                                            final Point currentPoint,
                                            final RouteNode lastNode, final AtomicReference<RouteNode> endNode){
        if(!searcedNodes.containsKey(currentPoint)){
            int maxY = maze.length -1;
            int maxX = maze[0].length -1;

            if(currentPoint.x == maxX && currentPoint.y == maxY){
                endLatch.countDown();
                endNode.set(new RouteNode(lastNode,currentPoint));
            }else{
                executorService.execute(new SearchThread(currentPoint,lastNode,executorService,endLatch,maze,searcedNodes,endNode));
            }
        }
    }
    public static void main(String[] args) throws InterruptedException {
        final int[][] maze = createMaze(50);
        final Point startPoint = new Point(0,0);
        final Map<Point,List<RouteNode>> searcedNodes = new ConcurrentHashMap<>();
        final CountDownLatch endLatch = new CountDownLatch(1);
        final AtomicReference<RouteNode> endNode = new AtomicReference<>(null);
        ExecutorService executorService = new ThreadPoolExecutor(1, Integer.MAX_VALUE, 60, TimeUnit.SECONDS,
                new SynchronousQueue<Runnable>(),
                new ThreadFactory() {
                    @Override
                    public Thread newThread(Runnable r) {
                        return new Thread(r, "thread-mazeSearch");
                    }
                }, new ThreadPoolExecutor.AbortPolicy());
        /*ExecutorService executorService = Executors.newSingleThreadExecutor();*/
        searchNextRouteNode(executorService,endLatch,maze,searcedNodes,startPoint,new RouteNode(null,null),endNode);
        endLatch.await();
        executorService.shutdownNow();

        RouteNode routeNode = endNode.get();
        StringBuilder stringBuilder = new StringBuilder();
        while ( routeNode != null ){
            if(routeNode.currenPoint != null){
                stringBuilder.insert(0,String.format("(%s,%s)=>",routeNode.currenPoint.x,routeNode.currenPoint.y));
            }
            routeNode = routeNode.lastRouteNode;
        }
        System.out.println(stringBuilder);
    }

}
